package com.isaiah.graph.adjacencylist;

import java.util.Stack;

/**
 * @Title: ${file_name}
 * @Description: ${todo}
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2020/6/816:30
 */
public class DepthFirstPaths {

    // 索引代表顶点，值表示当前顶点是否被访问过
    private boolean[] isVisited;

    // 起点
    private int s;

    // 索引代表顶点，值表示从起点s到当前顶点路径上的最后一个顶点
    private int[] edgeTo;

    public DepthFirstPaths(Graph g, int s) {
        // 初始化过isVisited数组
        this.isVisited = new boolean[g.V()];
        // 初始化起点
        this.s = s;
        // 初始化edgeTo数组
        this.edgeTo = new int[g.V()];
        dfs(g, s);
    }

    /**
     * 使用深度优先搜索找出G图中v顶点的所有相邻顶点
     * @param g
     * @param v
     */
    private void dfs(Graph g, int v) {
        // 把标记为已搜索
        isVisited[v] = true;
        // 遍历顶点v的邻接表，拿到每一个相邻的顶点，断续递归搜索
        for (Integer w : g.addj(v)){
            // 如果顶点w没有被搜索，拿到每个相邻的顶点，断续递归搜索
            if (!isVisited[w]){
                edgeTo[w] = v;  // 到达顶点w的路径上的最后一个顶点是v
                dfs(g, w);
            }
        }
    }

    /**
     * 判断w顶点与s顶点是否存在路径
     * @param v
     * @return
     */
    public boolean hasPathTo(int v){
        return isVisited[v];
    }

    /**
     * 找出从起点s到顶点v的路径(就是该路径经过的顶点)
     * @param v
     * @return
     */
    public Stack pathTo(int v){
        //当前v顶点与s顶点不连通，所以直接返回null，没有路径
        if (!hasPathTo(v)){
            return null;
        }
        // 创建栈对象，保存路径中的所有顶点
        Stack<Integer> path = new Stack<>();
        // 通过循环，从顶点v开始，一直往前找，到找到起点为止
        for (int x = v; x != s; x=edgeTo[x]){
            path.push(x);
        }
        // 把起点s放到栈中
        path.push(s);
        return path;
    }
}
